package leetcode316;

import java.math.BigInteger;
import java.util.Arrays;
import java.util.stream.IntStream;

/**
 * 暴力解但是 可以写出来
 * 这个题 是真离谱 啊
 * 
 * 
 * 这个题 本质上就是个 ： 数学问题（很难）
 * 有一种思想 就是 :
 * 可以将  cost[i] 看作是  nums[i] 出现的 次数. 
 * 这个题的 数学 考察的  比较多.
 */


public class leetcode6216使数组相等的最小开销 {

	public static void main(String args[]) {
		int nums[] = {1,3,5,2};
		int cost[] = {2,3,1,14};
		System.out.println(solution(nums,cost));
		
	}
	
	/**
	 * 这 个写法是 有问 题的 ！
	 * 至少 是 正确的最暴力的写法
	 */
	
	public static long solutionError(int nums[],int cost[]) {
//		long ans = Long.MAX_VALUE;
		BigInteger ans = BigInteger.valueOf(Long.MAX_VALUE * Long.MAX_VALUE);
		for(int i = 0;i < nums.length;i++) {
//			long min = 0;
			BigInteger min = BigInteger.ZERO;
			for(int j = 0;j < nums.length;j++) {
//				if(i == j)
//					continue;
//				min += Math.abs((nums[j] - nums[i]) ) *  cost[j];
				min.add(BigInteger.valueOf(nums[j] - nums[i]).abs().multiply(BigInteger.valueOf(cost[j])));
//				min.abs()
			}
//			ans = Math.min(min, ans);
			ans = ans.min(min);
		}
		
		return ans.longValue();
	}
	
	
	/**
	 * 前缀和的 几种写法
	 * 1.可以使用数组 PreSum [] 来保存前缀和 ，这种也是最常见的
	 * 
	 * 2. 直接使用一个sum 变量 ，来保存 前缀和 ， 
	 * 上面两种各有各的  应用场景
	 * 
	 * 但是 方式一：
	 * 这种的  适用性 更强！
	 * 
	 *  这道题 就是用   变量 sum 的形式 来存储 前缀和  
	 * 
	 */
	public static long solution(int nums[],int cost[]) {
//		long ans = Long.MAX_VALUE;
		int len = nums.length;
		
		/**
		 * 下面这种 比较  ** 骚 **   的排序 方式
		 * 掌握  一手
		 */
		Integer index[] = new Integer [len];
		for(int i = 0;i < len;i++) {
			index[i] = i;
		}
		Arrays.sort(index,(a,b) -> nums[a] - nums[b]);
		// 求出起始值 initialTotal,并不断的更新 这个  min ,并在当前的  for循环 中顺便把  前缀和 sum 求出来 
		long sum = 0, min = 0;
		for(int i = 0;i < len;i++) {
			sum += cost[i];
//			min += (long)(nums[index[i]] - nums[index[0]]) * cost[index[i]];
			min += (long)(nums[i] - nums[index[0]]) * cost[i];
		}
		long ans = min;
		for(int i = 1;i < len;i++) {
			sum -= 2 * cost[index[i - 1]];
			min -= sum * (nums[index[i]] - nums[index[i - 1]]);
			ans = Math.min(ans, min);
		}
		
		return ans;
	}
	
	
	/**
	 *  大佬 Arignote 的 写法   
	 *  令人佩服
	 */
	
	public long minCost(int[] nums, int[] cost) {
		Integer[] index = new Integer[nums.length];
		for (int i = 0; i < nums.length; i++) {
			index[i] = i;
		}
		Arrays.sort(index, (o, p) -> nums[o] - nums[p]);
		long min = 0, curr = 0, sum = 0;
		for (int i = 0; i < nums.length; sum += cost[i++]) {
			min = curr += (long) (nums[i] - nums[index[0]]) * cost[i];
		}
		for (int i = 1; i < index.length; i++) {
			min = Math.min(min, curr -= (sum -= 2 * cost[index[i - 1]]) * (nums[index[i]] - nums[index[i - 1]]));
		}
		return min;
	}
	
	
	
}
class Solution {
//    public static void main(String[] args) {
//        int[] nums = {1,3,5,2};
//        int[] cost = {2,3,1,14};
//        System.out.println(new Solution().minCost(nums, cost));
//    }
    public long minCost(int[] nums, int[] cost) {
        int n = nums.length;
        //索引排序
        Integer[] ids = IntStream.range(0, n).boxed().toArray(Integer[]::new);
        Arrays.sort(ids,(a,b)->
            nums[a] - nums[b]
        );
        //cost和
        long costSum = Arrays.stream(cost).sum();
        //总开销
        long total = 0L;
        //先计算变成最小数字的总开销
        for(Integer id : ids){
            total += (long) (nums[id] - nums[ids[0]]) * cost[id];
        }
        //最终最小开销
        long ans = total;
        //前缀和，过程中计算，用于计算开销改变量
        long t = cost[ids[0]];
        for(int i = 1 ; i < n ; i ++){
            //开销变化
            total +=  (nums[ids[i]] - nums[ids[i - 1]]) * (t -( costSum - t));
            //更新最小开销
            ans = Math.min(ans,total);
            t += cost[ids[i]];
        }
        return ans;
    }
}